A highly optimized algorithm for continuous intersection join queries over moving objects

Abstract

Given two sets of moving objects with nonzero extents, the continuous intersection join query reports every pair of intersecting objects, one from each of the two moving object sets, for every timestamp. This type of queries is important for a number of applications, e. g., in the multi-billion dollar computer game industry, massively multiplayer online games like World of Warcraft need to monitor the intersection among players' attack ranges and render players' interaction in real time. The computational cost of a straightforward algorithm or an algorithm adapted from another query type is prohibitive, and answering the query in real time poses a great challenge. Those algorithms compute th..